The present invention relates to a motion vector detection method, a motion vector detection apparatus, and a data storage medium. More particularly, this invention relates to a block unit motion compensation coding process, i.e., a motion vector detection process of generating a motion vector at a high speed and with high precision, which motion vector is used in a process of efficiently coding an image signal for each block comprising a prescribed number of pixels, using a pixel value correlation between frames.
In recent years, we have greeted the age of multimedia in which audio, video and other data are integrally handled, and the conventional information media, i.e., means for transmitting information to men, such as newspapers, magazines, televisions, radios, and telephones, have been adopted as the targets of multimedia. Generally, xe2x80x9cmultimediaxe2x80x9d means media in which, not only characters, but also diagrams, speeches, and especially images are simultaneously expressed in relation with each other. In order to handle the conventional information media as the targets of multimedia, it is necessary to express the information into digital formats.
When the quantity of data possessed by each of the above-described information media is estimated as the quantity of digital data, in the case of characters, the data quantity for each character is 1xcx9c2 byte. However, in the case of speech, the data quantity is 64 kbits per second (quality for telecommunication). Further, in the case of moving picture, the required data quantity is more than 100 Mbits per second (quality for current television broadcasting). So, in the above-described information media, it is not practical to handle such massive data as it is in the digital format. For example, although visual telephones have already been put to practical use by ISDN (Integrated Services Digital Network) having a transmission rate of 64 kbpsxcx9c1.5 Mbps, it is impossible to transmit an image of a television camera as it is by the ISDN.
So, data compression technologies are demanded. For example, for visual telephones, the moving picture compression techniques based on the H.261 and H.263 standard which have been standardized by ITU-T (International Telecommunication Union-Telecommunication Sector) are employed. Further, according to the data compression technique based on MPEG1 standard, it is possible to record image data as well as audio data in an ordinary music CD (compact disk).
The MPEG (Moving Picture Experts Group) is an international standard of data compression for moving pictures, and the MPEG1 is the standard for compressing moving picture data to 1.5 Mbps, i.e., data of a television signal to about {fraction (1/100)}. Since the transmission rate of the targets to which MPEG1 standard is directed is limited to about 1.5 Mbps, in the MPEG2 which has been standardized to meet the demand for higher image quality, moving picture data is compressed to 2xcx9c15 Mbps.
Furthermore, under the existing circumstances, standardization of MPEG4 is now proceeded by the working group for standardization of MPEG1 and MPEG2 (ISO/IEC JTC1/SC29/WG11), and this MPEG4 enables coding and signal processing in object units, and thereby realizes new functions required in the age of multimedia. The MPEG4 has originally aimed at standardization of coding methods of low bit rates, but the target of standardization is now extended to more versatile coding methods of high bit rates which are adaptable to an interlaced image.
In the above-mentioned coding process, a process of coding an image signal using the pixel value correlation between frames, i.e., so-called inter-frame motion compensation coding is utilized, thereby realizing a substantial data compression (bit rate saving). In this inter-frame motion compensation coding, an image signal of a block to be processed as a coding target (hereinafter referred to also as a target block) is compared with an image signal corresponding to a frame which was subjected to the coding (image signal of a reference frame), in units of image spaces each comprising 16xc3x9716 pixels (macroblocks) or image spaces each comprising 8xc3x978 pixels (blocks). Then, positional information indicating a position of a region (prediction block) on the reference frame in which region an arrangement pattern of pixel values is most similar to that in the target block is detected as a motion vector corresponding to the target block. This motion vector is coded together with a differential signal (motion compensation error) between an image signal corresponding to the target block and an image signal corresponding to the prediction block (reference block).
FIG. 11 is a block diagram illustrating a prior art typical inter-frame motion compensation coding apparatus. To simplify the description, the macroblock comprising 16xc3x9716 pixels and the block comprising 8xc3x978 pixels are both referred to as a block, hereinafter. This inter-frame motion compensation coding apparatus (hereinafter abbreviated as coding apparatus) 1000 receives an image signal which is obtained by dividing an image signal corresponding to a prescribed object so that the divided image signal corresponds to the block, successively block by block. Then, the coding apparatus 1000 subjects the image signal for each block to the inter-frame motion compensation coding.
To be specific, the coding apparatus 1000 comprises a subtracter d1 for obtaining a difference Dt between an image signal St corresponding to a block to be processed as a coding target and an image signal (motion compensation data) Pt corresponding to a prediction block obtained from an image signal corresponding to a reference frame, an orthogonal transformer d2 for transforming the difference Dt obtained by the subtracter d1 into a frequency component Tt by the orthogonal transformation such as DCT (Discrete Cosine Transformation), a quantizer d3 for quantizing the frequency component Tt and outputting a quantized value Qt, and a variable length encoder d4 for coding the quantized value Qt and outputting coded data Et.
In addition, the coding apparatus 1000 comprises an inverse quantizer d5 for inverse quantizing the quantized value Qt to obtain a frequency component IQt, an inverse orthogonal transformer d6 for transforming the obtained frequency component IQt into image data (pixel value) ITt in the spatial region by a processing such as inverse DCT, an adder d7 for adding the obtained image data ITt and the motion compensation data Pt, and a frame memory d8 for temporarily containing an output Rt of the adder d7 as data to be referred to in the coding of a subsequent frame.
Further, the coding apparatus 1000 comprises a motion detector d9 for comparing the image signal St corresponding to the block to be processed with image data Ct of the reference frame stored in the frame memory d8, for each region on the reference frame, each region being the same size as the block to be processed, and deriving information (motion vector) MV for indicating the position of a region (prediction block) on the reference frame, which has the minimum difference between the image signal St and the image data Ct, and a motion compensator d10 for generating an address signal Ad for the frame memory d8 according to the detected motion vector MV, obtaining image data Mt of a region (prediction block) which is specified by a pixel position on the reference frame, on the basis of the address signal Ad, and outputting this image data as the motion compensation data Pt.
In the above-mentioned prior art coding apparatus 1000, in stead of directly coding the image signal St, an output of the low-energy subtracter d1 is coded, thereby increasing the compression efficiency. It is known that this compression efficiency is increased, the smaller the energy of the output (amplitude of an output signal) of the subtracter d1 is. Therefore, it is important for the motion detector d9 to detect the motion vector at a high speed and with high precision. When the motion vector is detected with high precision, the energy of the output of the subtracter d1 is reduced.
In FIG. 11, the image signal (image data) St is input to an input terminal i20 and the coded data Et is output from an output terminal o20. In the coding apparatus 1000 shown in FIG. 11, the frame memory d8 and the motion detector d9 constitute a motion vector detection apparatus 200 for detecting the motion vector. Hereinafter, this motion vector detection apparatus 200 will be described in detail.
FIG. 12 is a block diagram illustrating a structure of a prior art typical motion vector detection apparatus.
This motion vector detection apparatus 200 comprises the frame memory d8 for containing the image data Ct of the reference frame, a motion vector generator u1a for receiving information Sc indicating a motion vector search origin from outside, and outputting candidate motion vectors MVc for indicating plural pixel positions in the vicinity of the search origin, an error calculator u3a for calculating an error (motion compensation error) Dp between the pixel value (image data) Ct of the prediction block on the reference frame, which is indicated by the candidate motion vectors MVc, and the image signal (image data) St of the input block to be processed, and a minimum error selector u4a for monitoring the error Dp as output of the error calculator u3a, and selecting a candidate motion vector having the minimum error from the candidate motion vectors MVc as the output of the motion vector generator u1a, thereby to output the selected candidate motion vector as a motion vector MVs corresponding to the block to be processed. In this case, the motion detector d9 is constituted by the motion vector generator u1a, the error calculator u3a, and the minimum error selector u4a. 
In FIG. 12, the image signal (image data) St is input to a first input terminal i1 of the motion vector detection apparatus 200. The motion vector search origin information Sc is input to a second input terminal al i2 of the motion vector detection apparatus 200. for receiving. The motion vector MVs is output from an output terminal o1 of the detection apparatus 200. The motion vector search origin information Sc indicates a position where the search process for comparing the image signal Ct of the reference frame stored in the frame memory d8 with the input image signal St, thereby to detect the motion vector is started. A position on the reference frame corresponding to the same spatial position as the target block on the frame to be processed or a position on the reference frame indicated by a detected motion vector of a neighboring block in the vicinity of the target block is usually used as the start position of the search process. For example, as the neighboring block in the vicinity of the target block, a block next to the target block on the left is used.
Then, a description of an operation is given.
When the image signal St corresponding to the block to be processed as a coding target is input to the inter-frame motion compensation coding apparatus 1000, the subtracter d1 obtains the difference Dt between the image signal St of the block to be processed and the image signal (motion compensation data) Pt of the corresponding prediction block. This difference Dt is transformed by the orthogonal transformer d2 into the frequency component Tt by the orthogonal transformation process such as DCT (Discrete Cosine Transformation). This frequency component Tt is quantized by the quantizer d3 and the corresponding quantized value Qt is output to the variable length encoder d4. Then, this quantized value Qt is variable length coded by the variable length encoder d4 into a variable length code, and the coded data Et corresponding to the block to be processed is output from the encoder d4.
At this time, the quantized value Qt is inverse quantized by the inverse quantizer d5 into the frequency component IQt by the inverse quantization process. This frequency component IQt is transformed by the inverse orthogonal transformer d6 into the image data (pixel value) ITt in the spatial region. This image data ITt is added by the adder d7 to the motion compensation data (image signal corresponding to the prediction block) Pt, and reproduction data Rt corresponding to the block to be processed is generated. This reproduction data Rt is temporarily stored in the frame memory d8 as reference data which is referred to in the coding of an image signal corresponding to a frame subsequent to the processed frame.
In the motion detector d9, the image signal Ct corresponding to the reference frame, which is stored in the frame memory d8 is compared with the image signal St corresponding to the block to be processed. The positional information of a prescribed region (prediction block) of the same size as the block to be processed on the reference frame is derived from the motion detector d9 as the motion vector MV corresponding to the block to be processed. Then, in the motion compensator d10, the address Ad corresponding to the position on the reference frame indicated by this motion vector MV is generated. On the basis of this address Ad, the image data Mt corresponding to the prediction block is output from the frame memory d8 as the motion compensation data Pt corresponding to the block to be processed.
Next, an operation of the motion vector detection apparatus 200 comprising the motion detector d9 and the frame memory d8 will be described in more detail.
The motion vector generator u1a in the motion vector detection apparatus 200 outputs motion vectors for indicating plural pixel positions in the vicinity of the search origin as the candidate motion vectors MVc, on the basis of the vector search origin information Sc which is supplied from out side the apparatus. Then, the frame memory d8 outputs an image signal (motion compensation data) Ct corresponding to a block on the reference frame, which is indicated by the candidate motion vectors MVc. Then, the error calculator u3a calculates the differential signal (image error data) Dp between the motion compensation data Ct corresponding to each of the candidate motion vectors and the image signal of the target block. The minimum error selector u4a monitors this image error data Dp, and selects a candidate motion vector MVc having the minimum error data Dp from the plural candidate motion vectors MVc, thereby outputting the selected candidate motion vector as the motion vector (selected motion vector) MVs corresponding to the block to be processed.
This motion vector detection apparatus 200 has a simple structure. However, it has a problem that the operation amount in calculating the motion compensation error is increased in proportion to the range of search for the motion vector, i.e., the number of the candidate motion vectors generated by the motion vector generator u1a. 
In other words, for an image including an object having a large motion, the motion vector search in a wide range on the image space leads to the improvement in coding efficiency. Therefore, in order to increase the coding efficiency, it is important to reduce the error calculation having the maximum operation load among operation processings in the motion detection apparatus.
Accordingly, a hierarchical motion vector detection method is often used as a method for reducing the number of operation times for the error calculation in the motion vector detection apparatus.
FIG. 13 is a diagram for explaining a prior art motion vector detection method (three-step method) as an example of the hierarchical motion vector detection method.
In this three-step method, in the n-th hierarchy processing, the search is recurrently performed at eight neighboring positions around a search origin, i.e., an indication position indicated by a motion vector detected in the (nxe2x88x921)-th hierarchy processing, in a search range one-third the size of the search range of the (nxe2x88x921)-th hierarchy processing. Here, the eight neighboring positions are four neighboring positions which are in the upward, downward, leftward, and rightward directions of the indication position and four neighboring positions which are in the upper rightward, lower rightward, upper leftward, and lower leftward directions of the indication position.
In FIG. 13, a mark ∘ denotes a pixel as a constituent of a reference frame. The mark ∘ in which the number xe2x80x9c1xe2x80x9d is written denotes a pixel as a search target in the first hierarchy processing (first search target pixel), and this is a typical position of candidate prediction blocks (motion compensation blocks) indicated by the candidate motion vectors. Nine of the first search target pixels are shown on the reference frame in FIG. 13, including the pixel as the search origin.
Initially, in the first hierarchy motion detection process, with a pixel P0 as the search origin, image error data corresponding to a specified block which is specified by positions of the pixel P0 and its surrounding pixels P1a to P1h (i.e., an error of image data between the specified block and the block to be processed) is detected. In this case, the surrounding pixel P1b has the minimum image error data. Therefore, the second hierarchy motion detection process is performed with this pixel P1b as the search origin. The surrounding pixels P1a to P1h are positioned at intervals of 9 pixels from the pixel P0 as the search origin on lines parallel to the vertical direction, horizontal direction, and slanting directions with xc2x145-degree angle to the horizontal direction, all of which include the search origin.
Then, in the second hierarchy motion detection process, with the surrounding pixel P1b as the search origin, image error data corresponding to a specified block which is specified by positions of surrounding pixels P2a to P2h of the pixel P1b (i.e., an error of image data between the specified block and the block to be processed) is detected. In this case, the surrounding pixel P2e has the minimum image error data. Therefore, the third hierarchy motion detection process is performed with the pixel P2e as the search origin. The surrounding pixels P2a to P2h are positioned at intervals of 3 pixels from the pixel P1b as the search origin on lines parallel to the vertical direction, horizontal direction, and slanting directions with xc2x145-degree angle to the horizontal direction, all of which include the search origin of the second hierarchy motion detection process.
Finally, in the third hierarchy motion detection process, with the surrounding pixel P2e as the search origin, image error data corresponding to a specified block which is specified by positions of surrounding pixels P3a to P3h of the pixel P2e (i.e., an error of image data between the specified block and the block to be processed) is detected. Here, the surrounding pixel P3a has the minimum image error data. Therefore, a motion vector indicating this pixel P3a (diagonally shaded ∘) is decided as a motion vector corresponding to the block to be processed, which is detected by the three-step method. Here, the surrounding pixels P3a to P3h are positioned at intervals of one pixel from the pixel P2e as the search origin on lines parallel to the vertical direction, the horizontal direction, and slanting directions with xc2x145-degree angle to the horizontal direction, all of which include the search origin in the third hierarchy motion detection process.
In this three-step method, under conditions which are usually satisfied for image data, i.e., under conditions that the closer the pixel is to the search position having the minimum image error data, the smaller the image error data corresponding to the pixel becomes, the motion vector can be detected with almost the same precision as that of a method of simply calculating image error data directly for all pixel positions in the search range (all pixels on the reference frame), thereby to detect a motion vector having the minimum image error data.
In the motion detection process according to the three-step method shown in FIG. 13, the calculation times for image error data (hereinafter also referred to simply as an error) are 9 times in the first hierarchy processing, 8 times in the second hierarchy processing, and 8 times in the third hierarchy processing, resulting in 25 times in total. Therefore, it is evident that the number of error calculation times can be substantially reduced with relative to the method of simply calculating the error directly for the all pixel positions in the search range.
FIG. 14 is a diagram for explaining another prior art motion vector detection method.
In this motion vector detection method, a process of searching the position of a pixel having the minimum error (image error data) is performed with xc2xd-pixel precision.
In this xc2xd-pixel precision search process, an interpolation pixel having a virtual pixel value is defined between two adjacent pixels on the reference frame. And a motion vector which indicates a pixel position having the minimum image error data is searched on the reference frame including these interpolation pixels. Then, on the basis of the motion vector with xc2xd-pixel precision, which is obtained by this search process, the motion compensation with high precision of xc2xd pixel or less is performed. Here, the pixel value of the interpolation pixel is obtained by the interpolation operation for pixel values of pixels on both sides of the interpolation pixel.
This xc2xd-pixel precision search process is utilized to reduce the energy (amplitude level) of the output signal of the subtracter d1 in the coding apparatus shown in FIG. 11, thereby increasing the coding efficiency.
In this xc2xd-pixel precision search process, when a pixel value of the reference frame is read from the frame memory, a new process of generating the virtual pixel value of the interpolation pixel which is positioned between two adjacent pixels by the interpolation operation is required. Accordingly, in the first hierarchy search process, the motion detection process with integer pixel precision is performed for pixels which are indicated by full line marks ∘ in FIG. 14. Then, in the second hierarchy search process, with a pixel Pxe2x80x20 (see FIG. 14) detected in the first search process as the search origin, a pixel position having the minimum error is detected with restricting search target pixels to neighborhood pixels which are around and adjacent to the pixel Pxe2x80x20 (pixels Pxe2x80x21 to Pxe2x80x28 in FIG. 14). In this way, the motion vector with xc2xd-pixel precision can be detected.
These prior art hierarchy motion vector search processes have a feature that the search range is narrowed and the search density is increased in stages while the motion vector having the minimum error is always selected within the search range corresponding to each stage.
FIG. 15 is a block diagram illustrating the prior art hierarchy motion vector detection apparatus.
This hierarchy motion vector detection apparatus 201 comprises a first hierarchy motion detector for detecting a motion vector MV1s by the first hierarchy search process on the basis of positional information (hereinafter referred to also as motion vector search origin information) Sc indicating a motion vector search origin, which is input from outside, and a second hierarchy motion detector for detecting a motion vector MV2s by the second hierarchy search process on the basis of the motion vector MV1s obtained by the first hierarchy search process.
In this case, like the motion vector detection apparatus 200 shown in FIG. 12, the first hierarchy motion detector comprises a MV generator u1a for generating plural first candidate motion vectors MV1c on the basis of the motion vector search origin information Sc from outside, a frame memory u2 for containing image data of a reference frame, an error calculator u3a for calculating error data D1p between motion compensation data (image data of a candidate prediction block) C1t read out from the frame memory u2 on the basis of the first candidate motion vectors MV1c and image data St of an input target block, and a minimum error selector u4a for selecting a candidate motion vector having the minimum error data from the plural candidate motion vector MV1c on the basis of the error data D1p, as a first hierarchy motion vector MV1s. 
The second hierarchy motion detector comprises a MV generator u1b for generating plural second candidate motion vectors MV2c with a pixel position indicated by the first hierarchy motion vector MV1s as the search origin, a frame memory u2 for containing the image data of the reference frame, an error calculator u3b for calculating error data D2p between motion compensation data (image data of a candidate prediction block) C2t read from the frame memory u2 on the basis of the second candidate motion vectors MV2c and the image data St of the input target block, and a minimum error selector u4b for selecting a candidate motion vector having the minimum error data from the plural candidate motion vectors MV2c on the basis of the error data D2p, as a second hierarchy motion vector MV2s. The minimum error data D1pm is supplied to the error calculator u3b of the second hierarchy motion detector, from the minimum error selector u4a of the first hierarchy motion detector. Accordingly, it is unnecessary for the error calculator u3b to obtain error data corresponding to the search origin in the second hierarchy motion detection process.
In the motion vector detection apparatus 201, the frame memory u2 is commonly used by the first hierarchy motion detector and the second hierarchy motion detector. In FIG. 15, the image signal St of the target block is input to a first input terminal i1. The motion vector search origin information Sc is input to a second input terminal i2. The motion vector MV2s of the target block is output from an output terminal o1. The frame memory u2 shown in FIG. 15 is the same as the frame memory d8 as shown in FIGS. 11 and 12.
Next, a description is given of an operation.
In the first hierarchy motion detector in the motion vector detection apparatus 201 in FIG. 15, exactly the same search process as that in the motion vector detection apparatus 200 in FIG. 12 is performed, whereby a motion vector corresponding to the target block is generated as the first hierarchy motion vector MV1s. 
When the first hierarchy motion vector MV1s is input to the second hierarchy motion detector in the motion vector detection apparatus 201, with a pixel position on the reference frame which is indicated by the first hierarchy motion vector MV1s as the search origin, the plural second candidate motion vectors MV2c corresponding to surrounding pixels in the vicinity of the search origin are generated in the second hierarchy motion detector.
When the image data (motion compensation data) C2t read from the frame memory u2, corresponding to the candidate prediction block on the reference frame indicated by the second candidate motion vectors is input to the error calculator u3b, the error data D2p between the motion compensation data C2t and the image data St of the target block is calculated.
In the minimum error selector u4b, the error data D2p corresponding to the respective candidate motion vectors MV2c is input together with the plural candidate motion vectors MV2c generated by the MV generator u1b, and a candidate motion vector MV2c having the minimum error data is selected and output as the second hierarchy motion vector MV2s. 
The error data D1pm corresponding to the search origin in the motion vector generator u1b (i.e., motion vector selected by the minimum error selector u4a) is already calculated by the error calculator u3a and notified to the minimum error selector u4a. Therefore, when this minimum error data D1pm is notified from the minimum error selector u4a to the error calculator u3b, an operation for obtaining error data corresponding to the motion vector indicating the search origin in the second hierarchy motion detection process can be omitted in the error calculator u3b. 
FIG. 15 shows the motion vector detection apparatus 201 which detects the motion vector corresponding to the target block by the search process in two hierarchies. However, it is easily known by analogy that a structure of a motion vector detection apparatus which detects the motion vector corresponding to the target block by the search process in three hierarchies can be obtained by further adding another set of an error calculator, a minimum error selector, and a MV generator to the motion vector detection apparatus 200 shown in FIG. 12.
In addition, the prior art motion vector detection method is not limited to the method of performing the hierarchical search process as described with reference to FIGS. 13 and 14. There is another method of deciding a search direction for each pixel position with a motion vector search origin as a search starting position, thereby to search a pixel position having a smaller motion compensation error on the reference frame.
FIG. 16 is a diagram for explaining such a motion vector detection method of shifting the search position successively from the vector search origin, to obtain a pixel position having a smaller motion compensation error, and this figure shows an arrangement of pixels on a reference frame. In the figure, Ps0 and Psaxcx9cPsi each denotes a pixel on the reference frame.
This motion vector detection method is called xe2x80x9cOne at a timexe2x80x9d method. Hereinafter, a process flow of this motion vector detection method is described in more detail.
Here, assume that following relationships (1) to (3) stand as for the image data error (motion compensation error) SADs0 and SADsaxcx9cSADsi between a block on the reference frame which is specified by the respective pixels Ps0 and Psaxcx9cPsi shown in FIG. 16 and a block to be processed on a processed frame:
SADs0, SADsa greater than SADSbxe2x80x83xe2x80x83(1)
SADsb, SADsd greater than SADscxe2x80x83xe2x80x83(2)
SADsc, SADsfxcx9cSADsi greater than SADsexe2x80x83xe2x80x83(3)
In this motion vector detection method, initially in the first step, the search for the pixels Psa and Psb which are on the left and right of the pixel Ps0 as the search origin is performed on the reference frame.
In this case, the motion compensation error SADsb corresponding to the pixel Psb on the right of the search origin pixel Ps0 is smaller than the motion compensation errors SADs0 and SADsa corresponding to the search origin pixel Ps0 and the pixel Psa on its left (see the relationship (1)). Accordingly, in the following second step, the search for the pixels Ps0 and Psc which are on the left and right of the pixel Psb is performed.
The motion compensation error SADsc corresponding to the pixel Psc is smaller than the motion compensation errors SADs0 and SADSb corresponding to the pixels Ps0 and Psb (see the relationships (1) and (2)). Therefore, in the third step, the search for the pixels Psb and Psd which are on the left and right of the pixel Psc is performed.
The motion compensation error SADsc corresponding to the pixel Psc is smaller than the motion compensation errors SADsb and SADsd corresponding to the pixels Psb and Psd (see the relationship (2)) Therefore, in the fourth step, the search for the pixels Pse and Psf which are on the upper and lower sides of the pixel Psc is performed.
The motion compensation error SADse corresponding to the pixel Pse is smaller than the motion compensation errors SADsc and SADsf corresponding to the pixels Psc and Psf (see the relationship (3)). Therefore, in the fifth step, the search for the pixels Psg and Psh which are on the left and right of the pixel Pse is performed.
The motion compensation error SADse corresponding to the pixels Pse is smaller than the motion compensation errors SADsg and SADsh corresponding to the pixels Psg and Psh (see the relationship (3)). Therefore, in the sixth step, the search for the pixels Psi and Psc which are on the upper and lower sides of the pixel Pse is performed. In this case, the motion compensation error SADse corresponding to the pixel Pse is smaller than the motion compensation errors SADsi and SADsc corresponding to the pixels Psi and Psc (see the relationship (3)). Therefore, a motion vector indicating the position of the pixel Pse is decided as the motion vector for the block to be processed.
The numbers in the marks ∘ for showing pixels in FIG. 16 show pixels which are newly added as search targets in the respective first to sixth steps. For example, the number in the mark ∘ for showing the pixel Psc is xe2x80x9c2xe2x80x9d. This number xe2x80x9c2xe2x80x9d means that this pixel Psc is newly added as the search target in the second step.
As described above, in the prior art motion vector detection process, the number of calculation times for image error data is substantially reduced by the efficient motion vector search such as the hierarchical motion vector search or xe2x80x9cOne at a timexe2x80x9d search. However, in recent years, the demand for the miniaturization of devices or energy savings is becoming increasingly exacting. Accordingly, there emerges the need for further reducing the number of calculation times for error data in the motion vector detection process.
Needless to say, the coding efficiency for image signals (image quality improvement at a prescribed bit rate) is critical in a use for the above-mentioned energy-saving micro image displaying device. However, the number of calculation times in the processes which require a large operation amount, such as the motion vector detection, should be further more reduced.
It is an object of the present invention to provide a motion vector detection method and a motion vector detection apparatus which can reduce the number of calculation times in the motion vector detection process which requires a large operation amount, with almost no deterioration in the coding efficiency for the image signals, thereby reducing the consumed power, and a data storage medium which contains a program for causing a computer to execute a process of detecting a motion vector by the motion vector detection method.
Other objects and advantages of the present invention will become apparent from the detailed description and specific embodiments described are provided only for illustration since various additions and modifications within the spirit and scope of the invention will be apparent to those of skill in the art from the detailed description.
A motion vector detection method according to a 1st aspect of the present invention, including a motion vector detection process of searching a position of a prediction block, corresponding to a block to be processed as a processing target, on a reference frame under a prescribed condition, for each block comprising a predetermined number of pixels as a unit for processing image data of a frame to be processed, thereby to detect information indicating the position of the prediction block as a motion vector corresponding to the block to be processed, comprises: a calculation process of calculating an error of image data between a block corresponding to a motion vector search origin as a position where search of the position of the prediction block is started, and the block to be processed as the processing target, as a motion compensation error corresponding to the motion vector search origin; and a comparison process of comparing a motion compensation error corresponding to a neighboring block in the vicinity of the block to be processed, which is an error of image data between the neighboring block and a prediction block corresponding thereto, with the motion compensation error corresponding to the motion vector search origin, and switching between outputting positional information indicating the motion vector search origin as the motion vector corresponding to the block to be processed, according to a comparison result between both of the motion compensation errors, as the motion vector corresponding to the block to be processed, and outputting a motion vector which is obtained by performing the motion vector detection process with the motion vector search origin as a search starting position, as the motion vector corresponding to the block to be processed.
According to a 2nd aspect of the present invention, the motion vector detection method of the 1st aspect comprises: when the motion compensation error corresponding to the motion vector search origin is smaller than the motion compensation error corresponding to the neighboring block, outputting the positional information indicating the motion vector search origin as it is as the motion vector corresponding to the block to be processed.
According to a 3rd aspect of the present invention, the motion vector detection method of the 1st aspect comprises: when the motion compensation error corresponding to the motion vector search origin is smaller than the motion compensation error corresponding to the neighboring block and the motion compensation error corresponding to the motion vector search origin is smaller than a predetermined value, outputting the positional information indicating the motion vector search origin as it is, as the motion vector corresponding to the block to be processed.
According to a 4th aspect of the present invention, the motion vector detection method of the 3rd aspect comprises: when a motion detection instruction signal is input from outside, outputting a motion vector which is obtained by performing the motion vector detection process with the motion vector search origin as the search starting position, as the motion vector corresponding to the block to be processed, regardless of size relationship between the motion compensation error corresponding to the neighboring block and the motion compensation error corresponding to the motion vector search origin.
According to a 5th aspect of the present invention, the motion vector detection method of the 1st aspect comprises: when a magnitude of a difference between the motion compensation error corresponding to the neighboring block and the motion compensation error corresponding to the motion vector search origin is smaller than a predetermined value, outputting the positional information indicating the motion vector search origin as it is, as the motion vector corresponding to the block to be processed.
A motion vector detection method according to a 6th aspect of the present invention, of searching a position of a prediction block, corresponding to a block to be processed as a processing target, on a reference frame under a prescribed condition, for each block comprising a predetermined number of pixels as a unit for processing image data of a frame to be processed, thereby to detect information indicating the position of the prediction block as a motion vector corresponding to the block to be processed, comprises: a process of searching the position of the prediction block in a first search range which is set on the reference frame, and calculating a first motion compensation error as an error of image data between a block on the reference frame, which block is specified by a first candidate motion vector corresponding to the block to be processed, and the block to be processed on the processed frame; a process of searching the position of the prediction block in a second search range on the reference frame in the vicinity of a pixel position indicated by the first candidate motion vector, and calculating a second motion compensation error as an error of image data between a block on the reference frame, which block is specified by a second candidate motion vector corresponding to the block to be processed, and the block to be processed on the processed frame; a process of searching the position of the prediction block in a third search range on the reference frame, which range is set on the basis of the first candidate motion vector and second candidate motion vector, and calculating a third motion compensation error as an error of image data between a block on the reference frame, which block is specified by a third candidate motion vector corresponding to the block to be processed, and the block to be processed on the processed frame; and a process of comparing the first, second, and third motion compensation errors, and selecting one of the first, second, and third candidate motion vectors as the motion vector corresponding to the block to be processed, according to a result of the comparison.
According to a 7th aspect of the present invention, in the motion vector detection method of the 6th aspect, the third search range is set in a region other than the first and second search ranges on the reference frame; and the position of the prediction block is searched in the third search range without referring to the first and second motion compensation errors.
According to an 8th aspect of the present invention, in the motion vector detection method of the 6th aspect, in the first search range, the position of the prediction block is searched in pixel units; and in the third search range, the position of the prediction block is searched by interpolating a pixel value corresponding to a virtual pixel between pixels of the reference frame and with precision higher than xc2xd-pixel precision.
According to a 9th aspect of the present invention, in the motion vector detection method of the 6th aspect, in the second search range, the position of the prediction block is searched only in a vertical or horizontal direction on the reference frame, and in the third search range, the position of the prediction block is searched in a direction other than the direction of the second search range.
A motion vector detection apparatus according to a 10th aspect of the present invention, which performs a motion vector detection process of searching a position of a prediction block, corresponding to a block to be processed as a processing target, on a reference frame under a prescribed condition, for each block comprising a predetermined number of pixels as a unit for processing image data of a frame to be processed, thereby to detect information indicating the position of the prediction block, as a motion vector corresponding to the block to be processed, comprises: an error calculation unit for calculating an error of image data between a block corresponding to a motion vector search origin as a position where search of the position of the prediction block is started, and the block to be processed as the processing target, as a motion compensation error corresponding to the motion vector search origin; a comparison unit for comparing a motion compensation error corresponding a neighboring block in the vicinity of the block to be processed, which is an error of image data between the neighboring block and a prediction block corresponding thereto, with the motion compensation error corresponding to the motion vector search origin; a decision unit for deciding whether the motion vector detection process for the block to be processed is to be performed, according to a result of the comparison of the motion compensation errors; a motion detection unit for detecting a motion vector by performing the motion vector detection process with the motion vector search origin as a search starting position, only when the decision unit decides that the motion vector detection process is to be performed; a selection unit for outputting the motion vector detected by the motion detection unit as the motion vector corresponding to the block to be processed when the decision unit decides that the motion vector detection process is to be performed, and outputting positional information indicating the motion vector search origin as it is as the motion vector corresponding to the block to be processed, when the decision unit decides that the motion vector detection process is not to be performed; and a memory for temporarily containing the motion compensation error corresponding to the motion vector output from the selection unit, as data for deciding whether the motion vector detection process for other blocks is to be performed.
A motion vector detection apparatus according to an 11th aspect of the present invention, for searching a position of a prediction block, corresponding to a block to be processed as a processing target, on a reference frame under a prescribed condition, for each block comprising a predetermined number of pixels as a unit for processing image data of a frame to be processed, thereby to detect information indicating the position of the prediction block as a motion vector corresponding to the block to be processed, comprises: a first motion detection unit for searching the position of the prediction block in a first search range which is set on the reference frame, and calculating a first motion compensation error as an error of image data between a block on the reference frame, which block is specified by a first candidate motion vector corresponding to the block to be processed, and the block to be processed on the processed frame; a second motion detection unit for searching the position of the prediction block in a second search range on the reference frame, which is in the vicinity of a pixel position indicated by the first candidate motion vector, and calculating a second motion compensation error as an error of image data between a block on the reference frame, which block is specified by a second candidate motion vector corresponding to the block to be processed, and the block to be processed; a third motion detection unit for searching the position of the prediction block in a third search range on the reference frame, which is set on the basis of the first candidate motion vector and second candidate motion vector, and calculating a third motion compensation error as an error of image data between a block on the reference frame, which block is specified by a third candidate motion vector corresponding to the block to be processed, and the block to be processed; and a selection unit for comparing the first, second, third motion compensation errors, and selecting one of the first, second, third candidate motion vectors as the motion vector corresponding to the block to be processed, according to a result of the comparison.
A data storage medium according to a 12th aspect of the present invention contains a program, and in the data storage medium, the program makes a computer perform a process of detecting a motion vector corresponding to a block to be processed, according to the motion vector detection method of the 1st aspect.
A data storage medium according to a 13th aspect of the present invention, contains a program, and in the data storage medium, the program makes a computer perform a process of detecting a motion vector corresponding to a block to be processed, according to the motion vector detection method of the 6th aspect.
According to the 1st, 2nd, 3rd, 4th, 5th, 10th, and 12th aspects of the present invention, the number of times of error calculation which requires the largest operation amount can be reduced without scarcely deteriorating the motion detection precision. Accordingly, the consumed power can be reduced, for example. Therefore, the motion vector detection process having a high practicality can be realized.
According to the 6th, 7th, 8th, 9th, 11th, and 13th aspects, the third search range can be efficiently narrowed and the number of error calculation times can be reduced.